package matrix;

/**
 * 3363. 最多可收集的水果数目
 * <p>
 * 有一个游戏，游戏由 n x n 个房间网格状排布组成。
 * 给你一个大小为 n x n 的二维整数数组 fruits ，其中 fruits[i][j] 表示房间 (i, j) 中的水果数目。
 * 有三个小朋友 一开始 分别从角落房间 (0, 0) ，(0, n - 1) 和 (n - 1, 0) 出发。
 * <p>
 * 每一位小朋友都会 恰好 移动 n - 1 次，并到达房间 (n - 1, n - 1) ：
 * <p>
 * 从 (0, 0) 出发的小朋友每次移动从房间 (i, j) 出发，可以到达 (i + 1, j + 1) ，(i + 1, j) 和 (i, j + 1) 房间之一（如果存在）。
 * 从 (0, n - 1) 出发的小朋友每次移动从房间 (i, j) 出发，可以到达房间 (i + 1, j - 1) ，(i + 1, j) 和 (i + 1, j + 1) 房间之一（如果存在）。
 * 从 (n - 1, 0) 出发的小朋友每次移动从房间 (i, j) 出发，可以到达房间 (i - 1, j + 1) ，(i, j + 1) 和 (i + 1, j + 1) 房间之一（如果存在）。
 * 当一个小朋友到达一个房间时，会把这个房间里所有的水果都收集起来。
 * 如果有两个或者更多小朋友进入同一个房间，只有一个小朋友能收集这个房间的水果。
 * 当小朋友离开一个房间时，这个房间里不会再有水果。
 * <p>
 * 请你返回三个小朋友总共 最多 可以收集多少个水果。
 * <p>
 * 示例 1：
 * 输入：fruits = [[1,2,3,4],[5,6,8,7],[9,10,11,12],[13,14,15,16]]
 * 输出：100
 * 解释：这个例子中：
 * 第 1 个小朋友的移动路径为 (0,0) -> (1,1) -> (2,2) -> (3, 3) 。
 * 第 2 个小朋友的移动路径为 (0,3) -> (1,2) -> (2,3) -> (3, 3) 。
 * 第 3 个小朋友的移动路径为 (3,0) -> (3,1) -> (3,2) -> (3, 3) 。
 * 他们总共能收集 1 + 6 + 11 + 16 + 4 + 8 + 12 + 13 + 14 + 15 = 100 个水果。
 * <p>
 * 示例 2：
 * 输入：fruits = [[1,1],[1,1]]
 * 输出：4
 * 解释：这个例子中：
 * <p>
 * 第 1 个小朋友移动路径为 (0,0) -> (1,1) 。
 * 第 2 个小朋友移动路径为 (0,1) -> (1,1) 。
 * 第 3 个小朋友移动路径为 (1,0) -> (1,1) 。
 * 他们总共能收集 1 + 1 + 1 + 1 = 4 个水果。
 */
public class Problem_3363 {

    public static void main(String[] args) {
        int[][] fruits = {
                {1, 2, 3, 4},
                {5, 6, 8, 7},
                {9, 10, 11, 12},
                {13, 14, 15, 16}
        };
        System.out.println(new Problem_3363().maxCollectedFruits(fruits));
    }

    public int maxCollectedFruits(int[][] fruits) {
        int result1 = fun1(fruits);
        handleFun(fruits);
        return result1 + fun2(fruits) + fun3(fruits);
    }


    // 第一个从 (0,0) 出发的小朋友 n-1 次到达 (n - 1, n - 1)，只能走对角线
    private int fun1(int[][] fruits) {
        int n = fruits.length;
        int result = 0;
        for (int i = 0; i < n; i++) {
            result += fruits[i][i];
            fruits[i][i] = 0;
        }
        return result;
    }

    private void handleFun(int[][] fruits) {
        int n = fruits.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - 1 - i; j++) {
                fruits[i][j] = 0;
            }
        }

    }


    // 第二个从 (0, n - 1) 出发的小朋友 n-1 次到达 (n - 1, n - 1)，只能走对角线的右上角,且每次移动必须要有向下位移
    private int fun2(int[][] fruits) {
        int n = fruits.length;
        int[][] dp = new int[n][n];
        dp[0][n - 1] = fruits[0][n - 1];

        // 从(0, n - 1) 出发，可移动方向为 (i + 1, j - 1) ，(i + 1, j) 和 (i + 1, j + 1)
        // 则经过第一次移动后，i一定等于1
        for (int i = 1; i < n; i++) {
            for (int j = n - 1; j >= n / 2; j--) {
                int max = 0;
                if (j + 1 <= n - 1) {
                    max = Math.max(max, dp[i - 1][j + 1]);
                }
                max = Math.max(max, dp[i - 1][j]);
                max = Math.max(max, dp[i - 1][j - 1]);
                dp[i][j] = fruits[i][j] + max;

            }

        }
        return dp[n - 1][n - 1];

    }

    // 第三个从 (n - 1, 0) 出发的小朋友 n-1 次到达 (n - 1, n - 1)，只能走对角线的左下角,且每次移动必须要向右位移
    private int fun3(int[][] fruits) {
        int n = fruits.length;
        int[][] dp = new int[n][n];
        dp[n - 1][0] = fruits[n - 1][0];

        // 从(n - 1, 0) 出发，可移动方向为  (i - 1, j + 1) ，(i, j + 1) 和 (i + 1, j + 1)
        // 则经过第一次移动后，j一定等于1
        for (int j = 1; j < n; j++) {
            for (int i = n - 1; i >= n / 2; i--) {
                int max = 0;
                if (i + 1 <= n - 1) {
                    max = Math.max(max, dp[i + 1][j - 1]);
                }
                max = Math.max(max, dp[i][j - 1]);
                max = Math.max(max, dp[i - 1][j - 1]);
                dp[i][j] = fruits[i][j] + max;
            }

        }
        return dp[n - 1][n - 1];

    }

}
